课程主页：

https://www.icourse163.org/course/NUDT-1003101005?tid=1460976445

斯坦福的编译原理课程感觉有些地方比较难理解，所以选择了中国大学MOOC上的课程进行补充，挑选后感觉国防科技大学的编译原理内容最全，所以决定学习这门课程。

这次回顾第1讲：引论。

第1讲 引论

什么是编译程序

翻译程序(Translator)

翻译程序是把某一种语言程序(称为源语言程序)等价地转换成另一种语言程序(称为目标语言程序)的程序。

编译程序(Compiler)

编译程序是把某一种高级语言程序等价地转换成另一种低级语言程序(如汇编语言或机器语言程序)的程序。

根据不同的用途和侧重，编译程序还可以进一步分为如下几类：

  • 诊断编译程序(Diagnostic Compiler)：帮助开发和调试。
  • 优化编译程序(Optimizing Compiler)：提高目标代码的效率。
  • 交叉编译程序(Cross Compiler)：运行编译程序的计算机叫宿主机，运行目标语言程序机器的机器叫目标机。如果编译程序产生出不同于宿主机的机器代码，那么就称其为交叉编译程序。
  • 可变目标编译程序(Retargetable Compiler)：不需要重写程序中与机器无关的部分，只要改变和目标机器有关的部分，就能针对不同的目标平台生成不同的目标机器上的代码，这类编译程序称为可变目标编译程序。
解释程序(Interpreter)

解释程序把源语言写的源程序作为输入，但不产生目标程序，而是边解释边执行源程序。

类比

背景是我们有一个英语说明书，但是工作人员只会中文，下面用两种方式使用说明书。

第一种方式是让别人将说明书翻译为中文，然后给工作人员使用，这种方式对应了编译：

第二种方式是请翻译人员将说明书逐句翻译，工作人员据此工作，这种方式对应了解释：

为什么要学习编译原理

计算思维
  • 计算思维包括一系列广泛的计算机科学的思维方法
    • 抽象
    • 自动化
    • 问题分解
    • 递归
    • 权衡
    • 保护、冗余、容错、纠错和恢复
    • 利用启发式推理来寻求解答
    • 在不确定情况下的规划、学习和调度
    • …
关于编译理论与技术
  • 编译理论与技术
    • 计算机科学与技术中理论和实践相结合的最好典范
  • 体现了很多典型的计算思维方法
  • ACM 图灵奖
    • 授予在计算机技术领域作出突出贡献的科学家
    • 程序设计语言、编译相关的获奖者是最多的
计算思维vs.编译
  • 抽象(Abstraction)
    • 忽略一个主题中与当前问题(或目标)无关的那些方面，以便更充分地注意与当前问题(或目标)有关的方面
    • 从众多的事物中抽取出共同的、本质性的特征，舍弃其非本质的特征
    • 是一种从个体把握一般、从现象把握本质的认知过程和思维方法
    • 编译原理中的”抽象”
      • 有限自动机
      • 形式文法
      • …
  • 自动化(Automation)
    • 将抽象思维的结果在计算机上实现，是一个将计算思维成果物化的过程，也是将理论成果应用于技术的实践
    • 自动化的思维方法不仅体现在编译程序本身的工作机制上，更体现在了编译程序的生成工具的研究和设计上
    • 编译原理中的”自动化“
      • 有限自动机
      • 预测分析程序
      • 算符优先分析
      • LR分析
      • …
  • 分解(Decomposition)
    • 将大规模的复杂问题分解成若干个较小规模的、更简单的问题加以解决
    • 编译原理中的”问题分解”
      • 为什么编译程序引入中间语言？
      • 为什么编译分成多个阶段？
      • 为什么分析过程分成多遍？
      • …
  • 递归(Recursion)
    • 编译原理中的”递归”
      • 递归下降分析
      • 基于树遍历的属性计算
      • 语法制导翻译
      • …
  • 权衡(折衷, Tradeoff )
    • 理论可实现vs. 实际可实现
    • 编译原理中的”权衡”
      • 用上下文无关文法来描述和处理高级程序设计语言
      • 优化措施的选择
      • …
学习编译原理的意义
  • 学习编译程序构造原理，技术
    • 提高对计算机系统总体认识
    • 感悟计算思维
    • 更好地理解“计算”
  • 更好地理解高级语言
  • 运用编译原理和方法构造实用工具
    • 用“计算”的眼光看世界
    • 用计算解决实际问题

编译过程

编译程序是怎样把高级语言(如C++)翻译成低级语言(如机器指令)的？将编译和翻译类比：

词法分析
  • 任务: 输入源程序，对构成源程序的字符串进行扫描和分解，识别出单词符号
  • 依循的原则：构词规则
  • 描述工具：有限自动机
语法分析
  • 任务：在词法分析的基础上，根据语法规则把单词符号串分解成各类语法单位(语法范畴)
  • 依循的原则：语法规则
  • 描述工具：上下文无关文法
中间代码产生
  • 任务：对各类语法单位按语言的语义进行初步翻译
  • 依循的原则：语义规则
  • 描述工具：属性文法
  • 中间代码：三元式，四元式，树，…
  • Z:=X + 0.618 * Y 翻译成四元式为
优化
  • 任务：对前阶段产生的中间代码进行加工变换，以期在最后阶段产生更高效的目标代码
  • 依循的原则：程序的等价变换规则
FOR K:=1 TO 100 DO
BEGIN  
    X := I+1;
    M := I + 10 * K;
    N := J + 10 * K;
END

优化前：

一共需要400次加法，200次乘法。

优化后：

一共需要301次加法。

目标代码产生
  • 任务: 把中间代码变换成特定机器上的目标代码
  • 依赖于硬件系统结构和机器指令的含义
  • 目标代码三种形式
    • 汇编指令代码: 需要进行汇编
    • 绝对指令代码: 可直接运行
    • 可重新定位指令代码: 需要连接

考虑如下例子：

分别开发模块A,B,C，每个模块中分别有程序a,b,c。模块可以相互组合，注意a在全部程序中的地址是无法确定的，但是其在A中的相对地址是可以确定的，这样编译出来的结果为可重定位的指令代码。

再来看一个具体例子：

机器指令的四个部分分别为操作码，寄存器操作数，操作数标志，第二操作数(地址)。

绿色部分的第一第三条为可重定位指令代码，加上偏移L之后得到可执行文件。

结构

编译程序总框

出错处理
  • 出错处理程序
    • 发现源程序中的错误，把有关错误信息报告给用户
  • 语法错误
    • 源程序中不符合语法（或词法）规则的错误
    • 非法字符、括号不匹配、缺少；、…
  • 语义错误
    • 源程序中不符合语义规则的错误
    • 说明错误、作用域错误、类型不一致、…
遍(pass)
  • 所谓”遍”， 就是对源程序或源程序的中间表示从头到尾扫描一次
  • 阶段与遍是不同的概念
    • 一遍可以由若干段组成
    • 一个阶段也可以分若干遍来完成
编译前端与后端

  • 编译前端
    • 与源语言有关，如词法分析，语法分析，语义分析与中间代码产生，与机器无关的优化
  • 编译后端
    • 与目标机有关，与目标机有关的优化，目标代码产生
  • 带来的好处
    • 程序逻辑结构清晰
    • 优化更充分，有利于移植

编译过程和编译程序结构之间的关系如下：

编译程序的生成

以汇编语言和机器语言为工具
  • 优点: 可以针对具体的机器，充分发挥计算机的系统功能；生成的程序效率高
  • 缺点: 程序难读、难写、易出错、难维护、生产的效率低
高级语言书写
  • 程序易读、易理解、容易维护、生产的效率高
  • 利用已有的某种语言的编译程序实现另一语言的编译程序
    • 现在已有利用A语言编写的L1到A的编译程序，要产生L2到A的编译程序，思路为利用L1语言编写L2到A的编译器C，然后利用L1到A的编译器编译C。
移植方法
  • 把一种机器上的编译程序移植到另一种机器上
  • 解释：假设我们已有L语言到A代码的编译器P1，现在利用L语言编写L语言到B代码的编译器P2，将P2输入P1，可以得到P2的A代码版本，接着将P2的L语言程序输入给P2的A代码版本，于是得到P2的B代码版本
自编译方式

先对L语言的核心部分L1利用低级语言实现编译程序，然后以L1为开发工具，实现L1+L2的部分的编译器，以此类推实现整个L的编译器。

编译程序自动产生
  • 编译程序-编译程序，编译程序产生器，编译程序书写系统
  • LEX：词法分析程序产生器
  • YACC：语法分析程序产生器

这些工具的工作模式如下：